#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1000010;
int rk[N],rk2[N],sa[N];
int n,k;
char s[N];

bool cmp(int i,int j){
    if(rk[i]!=rk[j])return rk[i]<rk[j];
    int ri=(i+k<=n?rk[i+k]:-1);
    int rj=(j+k<=n?rk[j+k]:-1);
    return ri<rj;
}

void getsa(){
    for(int i=1;i<=n;i++){
        sa[i]=i;
        rk[i]=s[i];
    }
    for(k=1;k<=n;k*=2){
        sort(sa+1,sa+1+n,cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++){
            rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
        }
        for(int i=1;i<=n;i++){
            rk[i]=rk2[i];
        }
    }
}

int ht[N];
void getht(){
    for(int i=1;i<=n;i++){
        rk[sa[i]]=i;
    }
    int h=0;
    for(int i=1;i<=n;i++){
        int j=sa[rk[i]-1];
        if(h>0){
            h--;
        }
        while(j+h<=n&&i+h<=n){
            if(s[j+h]!=s[i+h]){
                break;
            }
            h++;
        }
        ht[rk[i]]=h;
    }
}

int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    
    cin>>s+1;
    n=strlen(s+1);
    getsa();
    for(int i=1;i<=n;i++){
        cout<<sa[i]-1<<" ";
    }
    cout<<'\n';

    getht();
    for(int i=1;i<=n;i++){
        cout<<ht[i]<<' ';
    }
    cout<<'\n';

    return 0;
}
